package leetcode;
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class ValidateBST {
    public boolean isValidBST(TreeNode root) {
        if (root == null)
            return true;
            
        Result rl, rr;
        if (root.left != null){
            rl = isBST2(root.left);
            if (!rl.isBinary || rl.max >= root.val)
                return false;
        }
        
        if (root.right != null){
            rr = isBST2(root.right);
             if (!rr.isBinary || rr.min <= root.val)
                return false;
        }
        
       return true;
    }
    
    public Result isBST2(TreeNode node){
        Result rl=null, rr=null;
        if (node.left != null){
            rl = isBST2(node.left);
            if (!rl.isBinary || rl.max >= node.val)
                return new Result(false, node.val, rl.max);
        }
        
        if (node.right != null){
            rr = isBST2(node.right);
             if (!rr.isBinary || rr.min <= node.val)
                return new Result(false, rr.min, node.val);
        }
        
        if (node.left == null && node.right ==null)
            return new Result(true, node.val, node.val);
        else if (rr == null){
             return new Result(true, rl.min, node.val);
        } else if (rl == null)
            return new Result(true, node.val, rr.max);
        else
            return new Result(true, rl.min, rr.max);
        
    }
    
}

class Result{
    boolean isBinary;
    int min;
    int max;
    
    public Result(boolean b, int min, int max){
        isBinary = b;
        this.min = min;
        this.max = max;
    }
    
}